#pragma once
#include<iostream>
#include<vector>
#include<queue>
#include<stack>
#include<algorithm>
#include<functional>
#include<assert.h>
using namespace std;

typedef enum COLOR
{
	RED,
	BLACK,
}COLOR;

template<class V>
struct RBTreeNode
{
	typedef  struct RBTreeNode<V> Self;
	V _data;
	COLOR _col;
	RBTreeNode* _left = nullptr;
	RBTreeNode* _right = nullptr;
	RBTreeNode* _parent = nullptr;
	RBTreeNode(const V& data, COLOR col = RED)
		:_data(data)
		, _col(col)
	{}

	bool operator!=(const Self& node) { return _data != node._data; }
	bool operator==(const Self& node) { return _data == node._data; }
	
};

template<class T,class Ref,class Ptr>
struct RBTreeIterator
{
	typedef RBTreeIterator<T, Ref, Ptr> Self;
	typedef RBTreeNode<T> node;
	node* _node;
	RBTreeIterator(node* n = nullptr)
		:_node(n)
	{}

	Self& operator++()
	{
		node* pnode = _node->_parent;
		if (_node->_right)
		{
			_node = _node->_right;
			while (_node->_left)
				_node = _node->_left;
		}
		else
		{
			while (pnode && _node == pnode->_right)
			{
				_node = pnode;
				pnode = pnode->_parent;
			}
			_node = pnode;
		}
		return *this;
	}

	Self& operator--()
	{
		node* pnode = _node->_parent;
		if (_node->_left)
		{
			_node = _node->_left;
			while (_node->_right)
				_node = _node->_right;
		}
		else
		{
			while (pnode && _node == pnode->_left)
			{
				_node = pnode;
				pnode = pnode->_parent;
			}
			_node = pnode;
		}
		return *this;
	}

	Ref operator*() { return _node->_data; }
	Ptr operator->() { return &_node->_data; }
	bool operator!=(const Self& s) { return _node != s._node; }
	bool operator==(const Self& s) { return _node == s._node; }

};

template<class K,class V,class GETVAL>
class RBTree
{
public:
	typedef K k;
	typedef V v;
	typedef struct RBTreeNode<v> node;
	typedef RBTreeIterator<V, V&, V*> Iterator;
	typedef RBTreeIterator<V, const V&, const V> const_Iterator;


	RBTree()= default;
	RBTree(const RBTree<K, V ,GETVAL>&t)
	{
		_root = Copy(t._root);
		_sz = t._sz;
	}
	~RBTree()
	{
		Destroy(_root);
		_root = nullptr;
	}
	Iterator begin()
	{
		node* root = _root;
		while (root && root->_left)
			root = root->_left;
		return { root };
	}
	Iterator end() { return { nullptr }; }
	const_Iterator begin()const
	{
		node* root = _root;
		while (root && root->_left)
			root = root->_left;
		return { root };
	}
	const_Iterator end()const { return { nullptr }; }


	pair<Iterator,bool> insert(const V& data)
	{
		node* newnode = new node(data);
		if (!_root)
			_root = newnode;
		else
		{
			node* cnode = _root;
			node* pnode = nullptr;
			const k& nkey = getval(newnode->_data);
			while (cnode)
			{
				const k& ckey = getval(cnode->_data);
				pnode = cnode;
				if (ckey < nkey)
					cnode = cnode->_right;
				else if (ckey > nkey)
					cnode = cnode->_left;
				else
					return { {cnode},false };
			}
			cnode = newnode;
			cnode->_parent = pnode;
			if (getval(cnode->_data) < getval(pnode->_data))
				pnode->_left = cnode;
			else
				pnode->_right = cnode;

			while (pnode && pnode != _root && pnode->_col == RED)
			{
				node* ppnode = pnode->_parent;
				node* unode = nullptr;
				if (ppnode)
					unode = ppnode->_left == pnode ? ppnode->_right : ppnode->_left;
				if (unode && unode->_col == RED)
				{
					unode->_col = BLACK;
					pnode->_col = BLACK;
					ppnode->_col = RED;
					cnode = pnode;
					pnode = ppnode;
				}
				else if (pnode == ppnode->_left)
				{
					if (cnode == pnode->_left)
						rotateR(ppnode);
					else
					{
						rotateL(pnode);
						rotateR(ppnode);
					}
					break;
				}
				else
				{
					if (cnode == pnode->_left)
					{
						rotateR(pnode);
						rotateL(ppnode);
					}
					else
						rotateL(ppnode);
					break;
				}
			}
		}
		_root->_col = BLACK;
		_sz++;
		return { {newnode},true };
	}

	void rotateL(node* cnode)
	{
		node* pnode = cnode->_parent;
		node* rnode = cnode->_right;
		node* rlnode = rnode->_left;

		rnode->_parent = pnode;
		if(pnode)
		{
			if (pnode->_left == cnode)
				pnode->_left = rnode;
			else
				pnode->_right = rnode;
		}

		cnode->_right = rlnode;
		if (rlnode)
			rlnode->_parent = cnode;

		cnode->_parent = rnode;
		rnode->_left = cnode;

		cnode->_col = RED;
		rnode->_col = BLACK;
		if (_root == cnode)
			_root = rnode;
	}
	void rotateR(node* cnode)
	{
		node* pnode = cnode->_parent;
		node* lnode = cnode->_left;
		node* lrnode = lnode->_right;

		lnode->_parent = pnode;
		if (pnode)
		{
			if (pnode->_left == cnode)
				pnode->_left = lnode;
			else
				pnode->_right = lnode;
		}

		cnode->_left = lrnode;
		if (lrnode)
			lrnode->_parent = cnode;

		cnode->_parent = lnode;
		lnode->_right = cnode;

		cnode->_col = RED;
		lnode->_col = BLACK;
		if (_root == cnode)
			_root = lnode;
	}

	//show data

	size_t size()const { return _sz; }
	size_t levelsize() { return _levelsize(_root); }
	size_t leafsize(){return _leafsize(_root);}
	void inorder() { _inorder(_root);}
	//check
	bool checktree()
	{
		if (_root->_col == RED)return false;
		int num = 0;
		node* cnode = _root;
		while (cnode)
		{
			if (cnode->_col == BLACK)
				num++;
			cnode = cnode->_left;
		}
		return _checktree(_root,num,0) == -1 ? false : true;
	}

private:
	//check
	bool _checktree(node* root,int bnum,int cnum)
	{
		if (!root)
			return bnum == cnum;
		if (root->_col == RED)
		{
			if (root->_left && root->_left->_col == RED)
				return false;
			if (root->_right && root->_right->_col == RED)
				return false;
		}
		if (root->_left && getval(root->_data) <= getval(root->_left->_data))
			return false;
		if (root->_right && getval(root->_data) >= getval(root->_right->_data))
			return false;
		int i = root->_col == BLACK ? 1 : 0;
		bool left = _checktree(root->_left,bnum,cnum + i);
		if (left == false)
			return false;
		return _checktree(root->_right,bnum, cnum + i);
	}
	//_show
	static void printcol(node* root)
	{
		if (root->_col == RED)
			cout << "RED" << ' ';
		else
			cout << "BLACK" << ' ';
	}
	size_t _levelsize(node* root)
	{
		if (!root)
			return 0;
		return max(_levelsize(root->_left), _levelorder(root->_right));
	}
	size_t _leafsize(node* root)
	{
		if (!root)
			return 0;
		if (!root->_left && !root->_right)
			return 1;
		return _leafsize(root->_left) + _leafsize(root->_right);
	}

	void _inorder(node* root)
	{
		if (!root)
			return;
		_inorder(root->_left);
		cout << getval(root->_data) <<' ';
		_inorder(root->_right);
	}

	//
	void Destroy(node* root)
	{
		if (!root)
			return;
		Destroy(root->_left);
		Destroy(root->_right);
		delete root;
	}

	node* Copy(node* root)
	{
		if (!root)
			return nullptr;
		node* newnode = new node(root->_data);
		newnode->_left = Copy(root->_left);
		newnode->_right = Copy(root->_right);
		return newnode;
	}

	size_t _sz = 0;
	node* _root = nullptr;
	GETVAL getval;
};
